//Sat May 28 11:22:38 CDT 2011
#include <vector>
#include <list>
#include <map>
#include <set>
#include <deque>
#include <queue>
#include <stack>
#include <bitset>
#include <algorithm>
#include <functional>
#include <numeric>
#include <utility>
#include <sstream>
#include <iostream>
#include <iomanip>
#include <cstdio>
#include <cmath>
#include <cstdlib>
#include <cctype>
#include <string>
#include <cstring>
#include <cstdio>
#include <cmath>
#include <cstdlib>
#include <ctime>
#define distance 100000

using namespace std;

class CubeRoll {
public:
	int getMinimumSteps(int initPos, int goalPos, vector<int> holePos) {
		if (goalPos < initPos) {
			goalPos ^= initPos;
			initPos ^= goalPos;
		}
		if (checkHole(initPos, goalPos, holePos) == false)
			return -1;
		//queue<int> q;
		//cost[initPos] = 1;
		//q.push(initPos);
		if (left != -1 && right != distance + 1) {
			queue<pair<int, int> > q;
			cost[initPos] = true;
			q.push(make_pair(initPos, 1));
			while (!q.empty()) {
				//int x = q.front();
				//int dist = cost[x];
				int x = q.front().first;
				int dist = q.front().second;
				q.pop();
				if (x == goalPos)
					return dist - 1;
				for (int i = 1; x + i * i < right; i++) {
					if (cost[x + i * i] == false) {
						q.push(make_pair(x + i * i, dist + 1));
						cost[x + i * i] = true;
					}
				}
				for (int i = 1; x - i * i > left; i++) {
					if (cost[x - i * i] == false) {
						q.push(make_pair(x - i * i, dist + 1));
						cost[x - i * i] = true;
					}
				}
			}
		}
		//
		//
		//
		//
		//
		return -1;
	}

	bool checkHole(int start, int end, vector<int> holePos) {
		left = -1;
		right = distance + 1;
		cost.clear();
		int N = holePos.size();
		for (int i = 0; i < N; i++) {
			if (holePos[i] >= start && holePos[i] <= end)
				return false;
			if (holePos[i] <= start)
				left = max(left, holePos[i]);
			if (holePos[i] >= end)
				right = min(right, holePos[i]);
			//cost[holePos[i]] = -1;
			cost[holePos[i]] = true;
		}
		return true;
	}

private:
	//	map<int, int> cost;
	map<int, bool> cost;
	int left;
	int right;
};

